package SubjectTree.Five;

import java.util.Deque;
import java.util.LinkedList;

import Utility.TreeNode;

public class ConvertBST {

/**
 * 难度：中等
 * 
 * 538. 把二叉搜索树转换为累加树
 * 	给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），
 * 	使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
 * 	提醒一下，二叉搜索树满足下列约束条件：
 * 		节点的左子树仅包含键 小于 节点键的节点。
 * 		节点的右子树仅包含键 大于 节点键的节点。
 * 		左右子树也必须是二叉搜索树。
 * 	注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
 * 	
 * 示例 1：
 * 	输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
 * 	输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
 * 	
 * 示例 2：
 * 	输入：root = [0,null,1]
 * 	输出：[1,null,1]
 * 	
 * 示例 3：
 * 	输入：root = [1,0,2]
 * 	输出：[3,3,2]
 * 	
 * 示例 4：
 * 	输入：root = [3,2,4,1]
 * 	输出：[7,9,4,10]
 * 	
 * 提示：
 * 	树中的节点数介于 0 和 104 之间。
 * 	每个节点的值介于 -104 和 104 之间。
 * 	树中的所有值 互不相同 。
 * 	给定的树为二叉搜索树。
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ConvertBST cbst = new ConvertBST();
		System.out.println(cbst.convertBST_1(TreeNode.MkTree("[1,0,2]")));
	}
	//自己写(递归)
	int pre = 0;
	public TreeNode convertBST(TreeNode root) {
		traversal(root);
		return root;
    }
	public void traversal(TreeNode root) {
		if(root==null)return;
		
		traversal(root.right);
		root.val += pre;
		pre = root.val;
		traversal(root.left);
	}
	//自己写(中序遍历)
	public TreeNode convertBST_1(TreeNode root) {
		Deque<TreeNode> deque = new LinkedList<>();
		TreeNode node = root;
		while(!deque.isEmpty() || node!=null) {
			while(node!=null) {
				deque.push(node);
				node = node.right;
			}
			node = deque.poll();
			node.val+=pre;
			pre = node.val;
			node = node.left;
		}
		return root;
    }
	//方法一：反序中序遍历
	int sum = 0;
	public TreeNode convertBST1(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
	//方法二：Morris 遍历
	public TreeNode convertBST2(TreeNode root) {
        int sum = 0;
        TreeNode node = root;

        while (node != null) {
            if (node.right == null) {
                sum += node.val;
                node.val = sum;
                node = node.left;
            } else {
                TreeNode succ = getSuccessor(node);
                if (succ.left == null) {
                    succ.left = node;
                    node = node.right;
                } else {
                    succ.left = null;
                    sum += node.val;
                    node.val = sum;
                    node = node.left;
                }
            }
        }
        return root;
    }
    public TreeNode getSuccessor(TreeNode node) {
        TreeNode succ = node.right;
        while (succ.left != null && succ.left != node) {
            succ = succ.left;
        }
        return succ;
    }
}
